home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / prgtools / mint / mntdoc01.zoo / mintdoc / cat3 / bsearch.3 < prev    next >
Encoding:
Text File  |  1993-03-03  |  3.8 KB  |  133 lines
  1.  
  2.  
  3.  
  4. BSEARCH(3)          MINTLIB LIBRARY FUNCTIONS          BSEARCH(3)
  5.  
  6.  
  7. N✓NA✓AM✓ME✓E
  8.        bsearch - binary search a sorted table
  9.  
  10. S✓SY✓YN✓NO✓OP✓PS✓SI✓IS✓S
  11.        #include <stdlib.h>
  12.  
  13.        void *bsearch(const void *key, const void *base,
  14.                      size_t total_elems, size_t elem_size,
  15.                      int (*compare)(const void *one, const void *two));
  16.  
  17. D✓DE✓ES✓SC✓CR✓RI✓IP✓PT✓TI✓IO✓ON✓N
  18.        bsearch  is a binary search routine generalized from Knuth
  19.        (6.2.1) Algorithm B. It returns a  pointer  into  a  table
  20.        indicating  where  a datum may be found. The table must be
  21.        previously sorted in increasing order according to a  pro-
  22.        vided comparison function.
  23.          - key points to a datum instance to be sought in
  24.            the table.
  25.          - base points to the element at the base of the table.
  26.          - total_elems is the number of elements in the table.
  27.          - elem_size is the size, in bytes, of each element
  28.            in the table.
  29.          - compare is the name of the comparison function,
  30.            which is called with two arguments that point to
  31.            the elements being compared. As the function must
  32.            return an integer less than, equal to, or greater
  33.            than zero, so must the first argument to be considered
  34.            be less than, equal to, or greater than the second.
  35.  
  36. E✓EX✓XA✓AM✓MP✓PL✓LE✓E
  37.        The example below searches a table containing pointers to
  38.        nodes consisting of a string and its length. The table is
  39.        ordered alphabetically on the string in the node pointed
  40.        to by each entry.
  41.  
  42.        This code fragment reads in strings and either finds the
  43.        corresponding node, in which case it prints out the string
  44.        and its length, or it prints an error message.
  45.            #include <stdio.h>
  46.            #include <stdlib.h>
  47.            #include <string.h>
  48.            #define TABSIZE 1000
  49.            struct node /* These are stored in the table */
  50.            {
  51.              char *string;
  52.              int length;
  53.            };
  54.  
  55.            struct node table[TABSIZE]; /* Table to be searched */
  56.                  .
  57.                  .
  58.                  .
  59.            {
  60.              struct node *node_ptr, node;
  61.  
  62.  
  63.  
  64. MiNT docs 0.1              3 March 1993                         1
  65.  
  66.  
  67.  
  68.  
  69.  
  70. BSEARCH(3)          MINTLIB LIBRARY FUNCTIONS          BSEARCH(3)
  71.  
  72.  
  73.              int node_compare(const struct *node1, const struct *node2);
  74.              char str_space[20]; /* space to read string into */
  75.              .
  76.              .
  77.              .
  78.              node.string = str_space;
  79.              while (scanf("%s", node.string) != EOF)
  80.              {
  81.                node_ptr = (struct node *)bsearch(&node, table, TABSIZE,
  82.                           sizeof(struct node), node_compare);
  83.                if (node_ptr != NULL)
  84.                  printf("string = %20s, length = %dn",
  85.                         node_ptr->string, node_ptr->length);
  86.                else
  87.                  printf("not found: %sn", node.string);
  88.              }
  89.            }
  90.  
  91.            /* Compare two nodes based on an alphabetical */
  92.            /* ordering of the string field.              */
  93.            int node_compare(const void *table_node, const void *key_node)
  94.            {
  95.              const struct node *table = (const struct node *)table_node;
  96.              const struct node *key = (const struct node *)key_node;
  97.  
  98.              return(strcmp(table->string, key->string));
  99.            }
  100.  
  101. S✓SE✓EE✓E A✓AL✓LS✓SO✓O
  102.        q✓qs✓so✓or✓rt✓t(✓(3✓3)✓)
  103.  
  104. N✓NO✓OT✓TE✓ES✓S
  105.        The comparison function need not compare  every  byte,  so
  106.        arbitrary  data  may be contained in the elements in addi-
  107.        tion to the values being compared.
  108.  
  109.        A NULL pointer is returned if the key cannot be  found  in
  110.        the table.
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130. MiNT docs 0.1              3 March 1993                         2
  131.  
  132.  
  133.